//Tue Apr 20 05:42:56 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class RoadOrFlightEasy
{
public:
	int minTime(int N, vector<int> roadTime, vector<int> flightTime, int K)
	{
		ncase = N;
		road = roadTime;
		flight = flightTime;
		M = K;
		vector<vector<int> > v(N + 1, vector<int> (K + 1, 0));
		v[0][0] = 0;
		for (int i = 1; i <= N; i++)
		{
			v[i][0] = v[i - 1][0] + roadTime[i - 1];
		}
		for (int i = 1; i <= K; i++)
		{
			v[0][i] = 0;
		}
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= K; j++)
			{
				v[i][j] = min(v[i - 1][j - 1] + flightTime[i - 1], v[i - 1][j]
						+ roadTime[i - 1]);

			}
		}
		int mmax = 10000;
		for (int i = 0; i <= K; i++)
		{
			mmax = min(mmax, v[N][i]);
			cout << v[N][i] << endl;
		}
		return mmax;
	}
};
